
#ifndef AFTERMATH_ALGEBRA_FRACTION_HPP_INCLUDED
#define AFTERMATH_ALGEBRA_FRACTION_HPP_INCLUDED

#include "factorization.hpp"

#include <cstdint>
#include <ostream>
#include <string>
#include <utility>

namespace aftermath
{
    namespace algebra
    {
        template <typename T>
        struct fraction
        {
        private:
            T m_numerator = 0;
            T m_denominator = 1;

        public:
            fraction() = default;

            // Also defines implicit conversion.
            fraction(const T& value)
                : m_numerator(value), m_denominator(1)
            {
            }

            fraction(const T& numerator, const T& denominator)
                : m_numerator(numerator), m_denominator(denominator)
            {
                if (denominator < 0)
                {
                    this->m_numerator = -this->m_numerator;
                    this->m_denominator = -this->m_denominator;
                }
            }

            void simplify()
            {
                T x = factorization::greatest_common_divisor(this->m_numerator, this->m_denominator);
                this->m_numerator /= x;
                this->m_denominator /= x;
            }

            void negate()
            {
                this->m_numerator = -this->m_numerator;
            }

            void subtract_from_one()
            {
                this->m_numerator = this->m_denominator - this->m_numerator;
            }

            void invert()
            {
                T temp = this->m_denominator;
                this->m_denominator = this->m_numerator;
                this->m_numerator = temp;
            }

            const T& numerator() const { return this->m_numerator; }
            T& numerator() { return this->m_numerator; }

            const T& denominator() const { return this->m_denominator; }
            T& denominator() { return this->m_denominator; }
            
            explicit operator double() const
            {
                return static_cast<double>(this->m_numerator) / this->m_denominator;
            }

            explicit operator T() const
            {
                return this->m_numerator / this->m_denominator;
            }

            fraction<T>& operator -()
            {
                this->negate();
                return *this;
            }

            fraction<T> operator +(const T& other) const
            {
                return fraction<T>(this->m_numerator + other * this->m_denominator, this->m_denominator);
            }

            fraction<T>& operator +=(const T& other)
            {
                this->m_numerator += other * this->m_denominator;
                return *this;
            }

            friend fraction<T> operator +(const T& left, const fraction<T>& right)
            {
                return fraction<T>(left * right.m_denominator + right.m_numerator, right.m_denominator);
            }

            fraction<T> operator +(const fraction<T>& other) const
            {
                return this->m_denominator == other.m_denominator ?
                    fraction<T>(this->m_numerator + other.m_numerator, this->m_denominator) :
                    fraction<T>(this->m_numerator * other.m_denominator + other.m_numerator * this->m_denominator, this->m_denominator * other.m_denominator);
            }

            fraction<T>& operator +=(const fraction<T>& other)
            {
                if (this->m_denominator == other.m_denominator) this->m_numerator += other.m_numerator;
                else
                {
                    this->m_numerator = this->m_numerator * other.m_denominator + other.m_numerator * this->m_denominator;
                    this->m_denominator *= other.m_denominator;
                }
                return *this;
            }

            fraction<T> operator -(const T& other) const
            {
                return fraction<T>(this->m_numerator - other * this->m_denominator, this->m_denominator);
            }

            fraction<T>& operator -=(T other)
            {
                this->m_numerator -= other * this->m_denominator;
                return *this;
            }

            friend fraction<T> operator -(const T& left, const fraction<T>& right)
            {
                return fraction<T>(left * right.m_denominator - right.m_numerator, right.m_denominator);
            }

            fraction<T> operator -(const fraction<T>& other) const
            {
                return this->m_denominator == other.m_denominator ?
                    fraction<T>(this->m_numerator - other.m_numerator, this->m_denominator) :
                    fraction<T>(this->m_numerator * other.m_denominator - other.m_numerator * this->m_denominator, this->m_denominator * other.m_denominator);
            }

            fraction<T>& operator -=(const fraction<T>& other)
            {
                if (this->m_denominator == other.m_denominator) this->m_numerator -= other.m_numerator;
                else
                {
                    this->m_numerator = this->m_numerator * other.m_denominator - other.m_numerator * this->m_denominator;
                    this->m_denominator *= other.m_denominator;
                }
                return *this;
            }

            fraction<T> operator *(const T& other) const
            {
                return fraction<T>(this->m_numerator * other, this->m_denominator);
            }

            fraction<T>& operator *=(const T& other)
            {
                this->m_numerator *= other;
                return *this;
            }

            friend fraction<T> operator *(const T& left, const fraction<T>& right)
            {
                return right * left;
            }

            fraction<T> operator *(const fraction<T>& other) const
            {
                return fraction<T>(this->m_numerator * other.m_numerator, this->m_denominator * other.m_denominator);
            }

            fraction<T>& operator *=(const fraction<T>& other)
            {
                this->m_numerator *= other.m_numerator;
                this->m_denominator *= other.m_denominator;
                return *this;
            }

            fraction<T> operator /(const T& other) const
            {
                return fraction<T>(this->m_numerator, this->m_denominator * other);
            }

            fraction<T>& operator /=(const T& other)
            {
                this->m_denominator *= other;
                return *this;
            }

            friend fraction<T> operator /(const T& left, const fraction<T>& right)
            {
                return fraction<T>(left * right.m_denominator, right.m_numerator);
            }

            fraction<T> operator /(const fraction<T>& other) const
            {
                return fraction<T>(this->m_numerator * other.m_denominator, this->m_denominator * other.m_numerator);
            }

            fraction<T>& operator /=(const fraction<T>& other)
            {
                this->m_numerator *= other.m_denominator;
                this->m_denominator *= other.m_numerator;
                return *this;
            }

            bool operator >(const T& other) const
            {
                return (this->m_numerator > this->m_denominator * other);
            }

            bool operator >=(const T& other) const
            {
                return (this->m_numerator >= this->m_denominator * other);
            }

            bool operator <(const T& other) const
            {
                return (this->m_numerator < this->m_denominator * other);
            }

            bool operator <=(const T& other) const
            {
                return (this->m_numerator <= this->m_denominator * other);
            }

            friend bool operator >(const T& left, const fraction<T>& right)
            {
                return left * right.m_denominator > right.m_numerator;
            }

            friend bool operator >=(const T& left, const fraction<T>& right)
            {
                return left * right.m_denominator >= right.m_numerator;
            }

            friend bool operator <(const T& left, const fraction<T>& right)
            {
                return left * right.m_denominator < right.m_numerator;
            }

            friend bool operator <=(const T& left, const fraction<T>& right)
            {
                return left * right.m_denominator <= right.m_numerator;
            }

            bool operator >(const fraction<T>& other) const
            {
                return (this->m_numerator * other.m_denominator > other.m_numerator * this->m_denominator);
            }

            bool operator >=(const fraction<T>& other) const
            {
                return (this->m_numerator * other.m_denominator >= other.m_numerator * this->m_denominator);
            }

            bool operator <(const fraction<T>& other) const
            {
                return (this->m_numerator * other.m_denominator < other.m_numerator * this->m_denominator);
            }

            bool operator <=(const fraction<T>& other) const
            {
                return (this->m_numerator * other.m_denominator <= other.m_numerator * this->m_denominator);
            }

            bool operator ==(const fraction<T>& other) const
            {
                return this->m_numerator == other.m_numerator &&
                    this->m_denominator == other.m_denominator;
            }

            bool operator !=(const fraction<T>& other) const
            {
                return !(this->operator ==(other));
            }

            friend std::ostream& operator <<(std::ostream& os, const fraction<T>& that)
            {
                return os << that.m_numerator << "/" << that.m_denominator;
            }

            // Returns the ceiling of the fraction (<n> / <d>), assuming T is an integral type.
            static T ceiling_of_frac(const fraction<T>& n, const fraction<T>& d)
            {
                // ceiling(n / d) = floor((n + d - 1) / d).
                // ceiling((a/b) / (e/f)) = ceiling(a f / (b e)) = floor((a f + b e - 1) / (b e)).
                return ((d.m_denominator * n.m_numerator + d.m_numerator * n.m_denominator) - 1) / (d.m_numerator * n.m_denominator);
            }

            // Returns the ceiling of the fraction (<n> / <d>), assuming T is an integral type.
            static T ceiling_of_frac(const T& n, const fraction<T>& d)
            {
                // ceiling(n / d) = floor((n + d - 1) / d).
                // ceiling(n / (a/b)) = ceiling(b n / a) = floor((b n + a - 1) / a).
                return ((d.m_denominator * n + d.m_numerator) - 1) / d.m_numerator;
            }

            // Returns the ceiling of the fraction (<n> / <d>), assuming T is an integral type.
            static T ceiling_of_frac(const fraction<T>& n, const T& d)
            {
                // ceiling(n / d) = floor((n + d - 1) / d).
                // ceiling((a/b) / d) = ceiling(a / (b d)) = floor((b d + a - 1) / (b d)).
                return ((n.m_denominator * d + n.m_numerator) - 1) / (n.m_denominator * d);
            }

            // Returns the ceiling of the fraction (<n> / <d>), assuming T is an integral type.
            static T ceiling_of_frac(const T& n, const T& d)
            {
                // ceiling(n / d) = floor((n + d - 1) / d).
                return ((n + d) - 1) / d;
            }
        };
    }
}

namespace std
{
    template <typename T>
    struct hash<aftermath::algebra::fraction<T>>
    {
        typedef aftermath::algebra::fraction<T> argument_type;
        typedef std::size_t result_type;

        result_type operator()(const argument_type& x) const
        {
            return std::hash<T>()(x.get_numerator()) ^ std::hash<T>()(x.get_denominator());
        }
    };
}

#endif // AFTERMATH_ALGEBRA_FRACTION_HPP_INCLUDED
